10405 - Longest common subsequence/p10405.cpp

   1 #include <iostream>
   2 #include <string>
   3
   4 #define MAX(a,b) ((a>b)?(a):(b))
   5
   6 using namespace std;
   7
   8 int dp[1001][1001];
   9
  10 int lcs(const string &s, const string &t){
  11   int m = s.size(), n = t.size();
  12   if (m == 0 || n == 0) return 0;
  13   for (int i=0; i<=m; ++i)
  14     dp[i][0] = 0;
  15   for (int j=1; j<=n; ++j)
  16     dp[0][j] = 0;
  17   for (int i=0; i<m; ++i)
  18     for (int j=0; j<n; ++j)
  19       if (s[i] == t[j])
  20         dp[i+1][j+1] = dp[i][j]+1;
  21       else
  22         dp[i+1][j+1] = MAX(dp[i+1][j], dp[i][j+1]);
  23   return dp[m][n];
  24
  25
  26
  27 }
  28
  29 int main(){
  30   string s, t;
  31   getline(cin, s);
  32   getline(cin, t);
  33   while (!cin.eof()){
  34     cout << lcs(s, t) << endl;
  35     getline(cin, s);
  36     getline(cin, t);
  37   }
  38   return 0;
  39 }